package 数据结构考纲.测试;

import 数据结构考纲.图.MGraph;

import java.util.*;

public class Graph {
    //判断是否是BFS
    public static boolean isBFS(MGraph g, int[] bfs) {
        //默认序列元素不重复，且范围合法
        ///从前向后对bfs中的序列进行检查，检查其后的元素是否是其相邻节点，若不是，则其相邻接点是否已经全部遍历，若不是则该序列不是BFS，若是，则继续，
        boolean[] visited = new boolean[g.vex_num];

        //能检查到该节点就说明该节点前的节点是符合BFS要求的
        int k = 1;      //BFS生成树的当前访问的节点的第一个孩子前面有多少个节点
        //从前向后对bfs中的序列进行检查
        for (int i = 0; i < bfs.length; i++) {
            int v = bfs[i];
            visited[v] = true;
            //获得其所有邻接点
            Set<Integer> sets = new HashSet<>();
            for (int j = 0; j < g.vex_num; j++) {
                if (g.edge[v][j] > 0 && !visited[j]) sets.add(j);
            }
            int last_k = k, size = sets.size();
            k += sets.size();   //下一轮的节点的第一个子节点前的节点数
            //去除遍历的邻接点
            for (int j = last_k; j < last_k + size && j < g.vex_num; j++) {
                if (sets.contains(j)) visited[j] = true;
                sets.remove(bfs[j]);
            }
            if (!sets.isEmpty()) {
                System.out.printf("在遍历节点" + v + "时，没有遍历所有的未访问邻接点，如" + sets.toString());
                return false;
            }
        }
        return true;
    }

    //判断是否是DFS
    public static boolean isDFS(MGraph g, int[] dfs) {
        //不考虑dfs元素重复情况

        //使用栈，将序列第一个元素入栈，
        // 检查下一个是否是栈顶邻边，
        //      若是  则将其入栈，
        //      若不是，
        //          若栈顶未访问的邻边已被遍历完 则出栈，
        //          若未遍历完，则该序列不是DFS

        boolean[] visited = new boolean[g.vex_num];
        Stack<Integer> stack = new Stack<>();
        stack.push(dfs[0]);
        visited[dfs[0]] = true;
        for (int k = 1; k < g.vex_num; k++) {
            int i = dfs[k];
            int v = stack.peek();
            if (g.edge[v][i] > 0) {     //该节点是栈顶的邻边
                stack.push(i);
                visited[i] = true;
            } else {    //该节点不是栈顶的邻边
                //检查栈顶的邻边是否全部访问
                boolean isall = true;
                for (int j = 0; j < g.vex_num; j++) {
                    if (g.edge[v][j] > 0 && !visited[j]) {
                        isall = false;
                        break;
                    }
                }

                //   若栈顶未访问的邻边已被遍历完 则出栈，
                if (isall) {
                    stack.pop();
                    while (!stack.isEmpty()) {
                        if (g.edge[stack.peek()][i] > 0) {
                            stack.push(i);
                            visited[i] = true;
                            break;
                        } else { //检查该栈顶的邻接点有无全部访问
                            isall = true;
                            v = stack.peek();
                            for (int j = 0; j < g.vex_num; j++) {
                                if (g.edge[v][j] > 0 && !visited[j]) {
                                    isall = false;
                                    break;
                                }
                            }
                            if (isall) {
                                stack.pop();
                            } else {
                                System.out.printf("遍历到顶点%s时，其邻接顶点未遍历完全，如：", g.vex[v]);
                                for (int j = 0; j < g.vex_num; j++) {
                                    if (g.edge[v][j] > 0 && !visited[j]) {
                                        System.out.printf("%s ", g.vex[j]);
                                    }
                                }
                                System.out.println();
                                return false;
                            }

                        }
                    }
                }
                //   若未遍历完，则该序列不是DFS
                else {
                    System.out.printf("遍历到顶点%s时，其邻接顶点未遍历完全，如：", g.vex[v]);
                    for (int j = 0; j < g.vex_num; j++) {
                        if (g.edge[v][j] > 0 && !visited[j]) {
                            System.out.printf("%s ", g.vex[j]);
                        }
                    }
                    System.out.println();
                    return false;
                }


            }

        }
        for (boolean b : visited) {
            if (!b) return false;
        }
        return true;
    }



    //now指的是当前访问bfs序列的下标, 方法存疑
    private static boolean isDFS2(MGraph g, int[] dfs, int now, boolean[] visited) {
        if (now == g.vex_num-1)
            return true;
        visited[dfs[now]] = true;
        boolean flag = true;
        for (int i = now + 1; i < g.vex_num; i++) {
            if (g.edge[dfs[now]][dfs[i]] > 0 && !visited[dfs[i]]) {
                flag = isDFS2(g, dfs, i, visited);
            } else {
                //存在未访问的路径，则不是DFS
                for (int j = 0; j < g.vex_num; j++) {
                    if (g.edge[dfs[now]][j] > 0 && !visited[j])
                        flag = false;
                }
            }
            if (!flag)
                break;
        }
        return flag;
    }

    public static boolean isDFS2(MGraph g, int[] dfs) {
        boolean[] visited = new boolean[g.vex_num];
        return isDFS2(g, dfs, 0, visited);
    }


    public static void main(String[] args) {
        String[][] edges = new String[][]{{"a", "b", "2"}, {"a", "c", "5"}, {"b", "c", "2"}, {"b", "d", "3"}, {"c", "d", "3"}, {"c", "e", "4"}, {"c", "f", "1"}, {"d", "e", "1"}, {"d", "f", "4"}, {"e", "f", "1"},};

        MGraph mGraph = new MGraph(edges, true);
        boolean bfs = Graph.isBFS(mGraph, new int[]{0, 1, 2, 3, 4, 5});
        boolean bfs1 = Graph.isBFS(mGraph, new int[]{0, 2, 1, 3, 4, 5});
        boolean bfs2 = Graph.isBFS(mGraph, new int[]{0, 2, 1, 4, 3, 5});
        boolean bfs3 = Graph.isBFS(mGraph, new int[]{0, 1, 2, 4, 3, 5});
        System.out.println("是否是BFS: " + bfs);
        System.out.println("是否是BFS: " + bfs1);
        System.out.println("是否是BFS: " + bfs2);
        System.out.println("是否是BFS: " + bfs3);

        boolean dfs = Graph.isDFS(mGraph, new int[]{0, 1, 2, 3, 4, 5});
        System.out.println("是否是DFS: " + dfs);
        boolean dfs2 = Graph.isDFS(mGraph, new int[]{0, 2, 1, 3, 4, 5});
        System.out.println("是否是DFS: " + dfs2);
        boolean dfs3 = Graph.isDFS(mGraph, new int[]{0, 2, 1, 4, 3, 5});
        System.out.println("是否是DFS: " + dfs3);
        boolean dfs4 = Graph.isDFS(mGraph, new int[]{0, 3, 2, 1, 3, 5});
        System.out.println("是否是DFS: " + dfs4);
        boolean dfs5 = Graph.isDFS(mGraph, new int[]{0, 1, 3, 5, 2, 4});
        boolean dfs5_2 = Graph.isDFS2(mGraph, new int[]{0, 1, 3, 5, 2, 4});
        System.out.println("是否是DFS: " + dfs5);
        System.out.println("是否是DFS: " + dfs5_2);
        boolean dfs6 = Graph.isDFS(mGraph, new int[]{0, 1, 3, 5, 4, 2});
        boolean dfs6_2 = Graph.isDFS2(mGraph, new int[]{0, 1, 3, 5, 4, 2});
        System.out.println("是否是DFS: " + dfs6);
        System.out.println("是否是DFS: " + dfs6_2);

    }
}
